package leetcode_周赛._2023._10;

import java.util.HashMap;
import java.util.Map;

/**
 * 第 368 场周赛
 * AC_2
 *
 * @author yezh
 * @date 2023/10/23 8:51
 */
public class _22 {

    /**
     * 2910. 合法分组的最少组数
     * 算法: 贪心
     * 时间复杂度: O(n)
     * 枚举 k, 对于每个数, 拆分成 c 个组, 每组 k 个, 分完后, 还会多出 r(r = n % k) 个数, 如果 r <= c, 则表示可以把这 r 个数一个一个地分给 k 个组
     * 例如: val = 31, k = 10, val 可以被分成 10 10 10 1, 把 1 分给前 3 个 10 的其中一个
     */
    public int minGroupsForValidAssignment(int[] nums) {
        Map<Integer, Integer> g = new HashMap<>();
        for (int num : nums) g.put(num, g.getOrDefault(num, 0) + 1);
        int minK = Integer.MAX_VALUE;
        for (Integer value : g.values()) minK = Math.min(minK, value);
        int ans = 0;
        while (minK >= 1) {
            for (Integer value : g.values()) {
                // c 上取整
                int c = (value + minK) / (minK + 1), r = value % minK;
                if (r > value / minK) {
                    ans = 0;
                    break;
                }
                ans += c;
            }
            if (ans != 0) return ans;
            --minK;
        }
        return -1;
    }

}

